public class Solution213 {
    public int rob(int[] nums) {
        if (nums.length==1){
            return nums[0];
        }
        int[] f=new int[nums.length];
        int[] g=new int[nums.length];
        f[0]=nums[0];
        g[1]=nums[0];
        for (int i=2;i<nums.length;i++){
            f[i]=Math.max(f[i-1],g[i-1]+nums[i]);
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        int ans=g[nums.length-1];
        f=new int[nums.length];
        g=new int[nums.length];
        for (int i=1;i<nums.length;i++){
            f[i]=Math.max(f[i-1],g[i-1]+nums[i]);
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        ans=Math.max(ans,Math.max(f[nums.length-1],g[nums.length-1]));
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution213().rob(new int[]{1,2,3}));
    }
}
